import sys
from collections import deque


class Edge:
    def __init__(self, to, cost, capacity, rev):
        self.to = to
        self.cost = cost
        self.capacity = capacity
        self.rev = rev


def main():
    # Read input
    n, m = map(int, sys.stdin.readline().split())

    # Initialize graph
    max_nodes = n + 3
    e = [[] for _ in range(max_nodes)]

    def add_edge(u, v, cost, cap):
        e[u].append(Edge(v, cost, cap, len(e[v])))
        e[v].append(Edge(u, -cost, 0, len(e[u]) - 1))

    # Add edges
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        add_edge(u, v, w, 1)
        add_edge(v, u, w, 1)

    # Add super source and sink
    s = n + 1
    t = n + 2
    add_edge(s, 1, 0, 2)  # Super source to node 1, capacity 2
    add_edge(n, t, 0, 2)  # Node n to super sink, capacity 2

    INF = float('inf')
    paths = [[], []]
    path_count = 0

    def min_cost_flow(s, t, cnt):
        nonlocal path_count
        res = 0
        while path_count < 2:
            # SPFA algorithm
            dist = [INF] * (cnt + 1)
            dist[s] = 0
            in_queue = [False] * (cnt + 1)
            q = deque([s])
            pre = [-1] * (cnt + 1)
            pre_edge = [0] * (cnt + 1)

            while q:
                u = q.popleft()
                in_queue[u] = False
                for i, edge in enumerate(e[u]):
                    if edge.capacity > 0 and dist[edge.to] > dist[u] + edge.cost:
                        dist[edge.to] = dist[u] + edge.cost
                        pre[edge.to] = u
                        pre_edge[edge.to] = i
                        if not in_queue[edge.to]:
                            in_queue[edge.to] = True
                            q.append(edge.to)

            if dist[t] == INF:
                break

            # Record path
            flow = INF
            v = t
            path = []
            while pre[v] != -1:
                u = pre[v]
                edge_index = pre_edge[v]
                flow = min(flow, e[u][edge_index].capacity)
                if 1 <= v <= n:  # Exclude super source and sink
                    path.append(v)
                v = u
            path.append(1)  # Add start node
            path.reverse()

            # Remove consecutive duplicates
            unique_path = []
            last = -1
            for node in path:
                if node != last:
                    unique_path.append(node)
                    last = node
            paths[path_count] = unique_path
            path_count += 1

            # Update residual network
            v = t
            while pre[v] != -1:
                u = pre[v]
                edge_index = pre_edge[v]
                e[u][edge_index].capacity -= flow
                e[v][e[u][edge_index].rev].capacity += flow
                v = u

            res += dist[t] * flow
        return res

    total_cost = min_cost_flow(s, t, n + 2)

    if path_count < 2:
        print("没有找到有效路径")
    else:
        print(f"最短总路径长度: {total_cost}")
        if paths[0]:
            print("去程:", " -> ".join(map(str, paths[0])))
        if paths[1]:
            return_path = paths[1][::-1]
            print("返程:", " -> ".join(map(str, return_path)))

if __name__ == '__main__':
    main()